/**
 * 数轴上有N个点坐标
 * 有Q个询问，每个询问：给定坐标b，问距离b的第k近距离是多少
 * 
 * 首先将N个点坐标排序，假设某个询问的第k近距离是d，
 * 说明[b - d, b + d]范围内恰好有k个点
 * 因此二分搜索即可
 */
#include <bits/stdc++.h>
#include <bits/extc++.h>
using namespace std;


using llt = long long;
using vi = vector<int>;
using vll = vector<llt>;
using pll = pair<llt, llt>;

llt const INF = 0x7F1F2F3F4F5F6F7F;


int N;
int M;

__gnu_pbds::tree<
    pll, __gnu_pbds::null_type, std::less<pll>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update
>T;

bool check(llt b, int k, llt dist){
    int ranka = T.order_of_key({b - dist, 0LL});
    int rankb = T.order_of_key({b + dist, N + N + 0LL});
    int cha = rankb - ranka;
    return cha < k;
}

llt proc(llt b, int k){
    llt left = 0, right = 1E9, mid;
    do{
        mid = (left + right) >> 1;
        if(check(b, k, mid)) left = mid + 1;
        else right = mid - 1;
    }while(left <= right);
    // cout << left << ", " << right << endl;
    return left;
}

void work(){ 
    cin >> N >> M;
    for(int i=0;i<N;++i){
        int a; cin >> a;
        T.insert({a + 0LL, i + 1LL});
    }
    // A.assign(N, {});
    // for(auto & i : A) cin >> i;

    // sort(A.begin(), A.end());
    
    for(int q=1;q<=M;++q){
        int b, k; cin >> b >> k;
        cout << proc(b, k) << "\n";
    }
	return;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);	
    int nofkase = 1;
	// cin >> nofkase;
	while(nofkase--) work();
	return 0;
}